Witnessing Control Flow Graph Optimizations
- Project Research
- 1-5 Chapters
- Abstract : Available
- Table of Content: Available
- Reference Style: APA
- Recommended for : Student Researchers
- NGN 3000
ABSTRACT
Proving the correctness of a program transformation, and specifically, of a compiler optimization, is a long-standing research problem. Trusting the compiler requires to guarantee that the properties verified on the source program hold for the compiled target-code as well. Thus, the primary objective of formal correctness verification is to preserve the semantics of the source code, maintaining untouched its logical behavior. Traditional methods for formal correctness verification are not convenient to validate large and complex programs like compilers [1], and intensive testing, despite its proven efficacy, cannot guarantee the absence of bugs [2]. This thesis is part of a larger on-going research project aimed to demonstrate the feasibility to overcome the difficulties of traditional formal methods. K. Namjoshi and L. Zuck [3] propose a new methodology for creating an automated proof to guarantee the correctness of every execution of an optimization. A witness is a run-time generated relation between the source code and the target code, before and after the transformation. The relation is able to represent all the properties that must be valid throughout the optimization, offering a mathematical formula to prove, through a SMT-Solver (typically Microsoft Z3 ), if the invariants hold and the semantics is preserved. This work is a further step towards the implementation of a witnessing compiler [4]: the SimplifyCFG pass of the LLVM compiler framework is augmented with a witness generator procedure which constructs, run-time, the relations to prove the correctness of every single simplification in the control flow graph, performed by the compiler. We show that it is feasible to augment the SimplifyCFG pass with a witness generation procedure. We describe the structure of the code and the mathematical relations designed to demonstrate the correctness of a transformation on the Control Flow Graph. Benchmarks and tests will prove the correct behavior of our implementation and the effectiveness of the witnessing procedure. We provide details about the witnesses and the results of the benchmarks. First, the problem is described, together with the limitations of the traditional methods; then a solution is designed and explained. Details about the actual implementation for the SimplifyCFG code are provided in further sections
Related Project Materials
THE INFLUENCE OF ENGLISH LANGUAGE ON OUR NIGERIAN INDIGENOUS LANGUAGES: EXAMPLES OF BORROWING FROM ENGLISH INTO YORUBA BY UNILORIN UNDERGRADUATES
ABSTRACT
Generally speaking, it seems unlikely that E...
KNOWLEDGE, ATTITUDE AND PRACTICES OF WOMEN TOWARDS FAMILY PLANNING SERVICES
ABSTRACT:- This study was carried out to assess the knowledge, attitude and practices of women towards famil...
PROBLEM OF PREGNANCY AND ABORTION ON GIRL-CHILD EDUCATION IN NIGERIA
ABSTRACT
This study was carried out to examine the problem of pregnancy and a...
DESIGN AND IMPLEMENTATION OF AN ONLINE BOOKSHOP MANAGEMENT SYSTEM WITH SYSTEM WITH E-PAYMENT INTEGRATION
BACKGROUND OF THE STUDY
On-line Book shopping entails buying and selling of books of all sorts with the buyer still maki...
THE USE OF LIBRARY AND STUDENTS ACADEMIC PERFORMANCE IN UNIVERSITIES
ABSTRACT
This study examined the use of the library and students’ academic performance at Univers...
AUDIT QUALITY AND CONCEPT OF GOING CONCERN IN QUOTED NON-FINANCIAL FIRMS IN NIGERIA
ABSTRACT
The objective of the study is to examine audit quality and concept of going concern in quoted nonfinancial companies in Nigeria....
ECONOMIC ANALYSIS OF PIG PRODUCTION
Background of the Stud...
THE INFLUENCE OF ETHICAL LEADERSHIP ON ORGANIZATIONAL BEHAVIOR
THE INFLUENCE OF ETHICAL LEADERSHIP ON ORGANIZATIONAL BEHAVIOR
This study examines the...
ROLE AND CONTRIBUTION OF NIGERIA IN THE COMMONWEATH OF NATIONS 1999 TO 2007
ABSTRACT
Nigeria external relations with the outside world started a long time before she gained her autonomy as an inde...
PERFORMANCE EVALUATION OF DIFFERENT MATERIALS AS CHILLS IN SAND CASTING OF ALUMINIUM ALLOY
ABSTRACT
This study has evaluated the effectiveness of metallic materials as chill in sand casting of aluminium alloy. Four plates of dim...
